package com.demo.java.OD251_300.OD295;

import java.util.Scanner;

/**
 * @author bug菌
 * @Source 公众号：猿圈奇妙屋
 * @des： 【光伏场地建设规划】问题
 * @url： https://blog.csdn.net/weixin_43970743/article/details/146088941
 */
public class OdMain {
    public static void main(String[] args) {
        // 输入行数、列数、边长和目标值
        Scanner scanner = new Scanner(System.in);
        int row = scanner.nextInt();
        int col = scanner.nextInt();
        int width = scanner.nextInt();
        int pow = scanner.nextInt();

        int[][] region = new int[row][col];

        // 输入矩阵数据
        for (int i = 0; i < row; i++) {
            for (int j = 0; j < col; j++) {
                region[i][j] = scanner.nextInt();
            }
        }

        // 计算前缀和
        int[][] prefixSum = calculatePrefixSum(region, row, col);

        int res = 0;

        // 遍历所有可能的子矩阵，计算其和并进行比较
        for (int i = 0; i < row - width + 1; i++) {
            for (int j = 0; j < col - width + 1; j++) {
                int count = calculateSubMatrixSum(prefixSum, i, j, width);
                if (count >= pow) {
                    res++;  // 如果子矩阵的和大于或等于目标值，则计数
                }
            }
        }

        // 输出结果
        System.out.println(res);
    }

    // 计算二维矩阵的前缀和
    private static int[][] calculatePrefixSum(int[][] matrix, int row, int col) {
        int[][] prefixSum = new int[row + 1][col + 1];

        // 填充前缀和矩阵
        for (int i = 1; i <= row; i++) {
            for (int j = 1; j <= col; j++) {
                prefixSum[i][j] = prefixSum[i - 1][j] + prefixSum[i][j - 1]
                        - prefixSum[i - 1][j - 1] + matrix[i - 1][j - 1];
            }
        }

        return prefixSum;
    }

    // 计算指定子矩阵的和
    private static int calculateSubMatrixSum(int[][] prefixSum, int row, int col, int width) {
        // 确定子矩阵的四个角
        int rowStart = row;
        int rowEnd = row + width - 1;
        int colStart = col;
        int colEnd = col + width - 1;

        // 使用前缀和公式计算子矩阵的和
        return prefixSum[rowEnd + 1][colEnd + 1] - prefixSum[rowEnd + 1][colStart]
                - prefixSum[rowStart][colEnd + 1] + prefixSum[rowStart][colStart];
    }
}